package Hot100;


/**
 * @author zhangmin
 * @create 2021-12-22 10:02
 */
public class longestValidParentheses32 {

    /**32. 最长有效括号
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     * 1、双指针，记录左右括号在窗口中出现的次数，当左括号==右括号时，可以得到合法字串，
     * 当 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0。
     * 接着，需要从右向左，再遍历一遍，当 left 计数器比 right 计数器大时，我们将 left 和 right 计数器同时变回 0，
     * */
    public int longestValidParentheses1(String s) {
        int n=s.length();
        if (n<=1) return 0;
        int res=0;
        int left=0,right=0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i)=='('){
                left++;
            }else right++;

            if (left==right){
                res=Math.max(res,2*right);
            }else if (right>left){
                left=right=0;
            }
        }
        left=right=0;
        for (int i = n-1; i >= 0; i--) {
            if (s.charAt(i)=='('){
                left++;
            }else {
                right++;
            }
            if (left==right){
                res=Math.max(res,right*2);
            }else if (left>right){
                left=right=0;
            }
        }
        return res;
    }

    /*
    * 2、动态规划
    * dp[i] 表示以下标 i 字符结尾的最长有效括号的长度
    * 显然有效的子串一定以 ‘)’ 结尾，因此我们可以知道以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ‘)’ 在 dp 数组中对应位置的值。
    * 从前向后遍历，每两个字符检查一次，
    * s[i]=‘)’ 且 s[i−1]=‘(’，也就是字符串形如 “……()”，我们可以推出：dp[i]=dp[i−2]+2
    * s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”，我们可以推出：如果 s[i - dp[i - 1] - 1] = ‘(’，那么dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2
    *          倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 sub_s），对于最后一个 ‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’ ，
    *          且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 sub_s的前面）
    * */
    public int longestValidParentheses(String s) {
        int n=s.length();
        if (n<=1) return 0;
        int[] dp=new int[n];
        dp[0]=0;
        int res=0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i)==')'){
                if (s.charAt(i-1)=='('){
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                }else if (i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i]=dp[i-1]+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0)+2;
                }
                res=Math.max(res,dp[i]);
            }
        }
        return res;
    }
}
